This invention relates to methods for establishing or restoring communications paths in networks, for example telecommunications networks, particularly upon the occurrence of a failure of one of the spans or nodes of the network.
The development of Digital Crossconnect Systems (DCS), and networks with physically diverse routes, promotes the use of mesh restoration. DCS machines are in many respects similar to a computer, and a transport network consisting of Digital Crossconnects is similar in many respects to a distributed multiprocessor. Mesh-based survivable or restorable network architectures exploit the intelligence of a DCS-based transport network to minimize the amount of spare capacity required to protect working demands. See: Bates, B., Gregory, D., Voice and Data Communications Handbook, New York, NY: McGraw-Hill Inc., 1996, Barezzani, M., Pedrinelli, E., Gerla, M., xe2x80x9cProtection planning in transmission networksxe2x80x9d, Proc. IEEE ICC""92, 1992, pp. 316.4.1-316.4.5. Chao, C. W., Fuoco, G., Kropfl, D., xe2x80x9cFASTAR platform gives the network a competitive edgexe2x80x9d, AT and T Technical Journal, July/August 1994, pp. 69-81. Chng, R. S. K., Botham, C. P., Johnson, D., Brown, G. N., Sinclair, M. C., O""Mahony, M. J. Hawker, I., xe2x80x9cA multi-layer restoration strategy for reconfigurable networksxe2x80x9d, Proc. IEEE Globecom ""94, December 1994, pp. 1872-1878. Chujo, T., Komine, H., Miyazaki, K., Ogura, T., Soejima, T., xe2x80x9cDistributed self-healing network and its optimum spare capacity assignment algorithmxe2x80x9d, Electronics and Communications in Japan, part 1, vol. 74, no. 7, 1991, pp. 1-8. Coan, B. A., Vecchi, M. P., Wu, L. T., xe2x80x9cA distributed protocol to improve the survivability of trunk networksxe2x80x9d, Proceedings of the 13th International Switching Symposium, May 1990, pp. 173-179. Coan, B. A., et al., xe2x80x9cUsing distributed topology updates and preplanned configurations to achieve trunk network survivabilityxe2x80x9d, IEEE Transaction on Reliability, vol. 40, no. 4, 1991, pp. 404-416. Davis, L., Cox, A., Qiu, Y., xe2x80x9cA Genetic Algorithm for Survivable Network Designxe2x80x9d, Proc. of the Fifth International Conference on Genetic Algorithms, July, 1993, pp. 408-415. These networks are called xe2x80x9cmesh restorablexe2x80x9d not to imply that the network is a full mesh, but to reflect the ability of the rerouting mechanism to exploit a mesh-like topology through highly diverse and efficient rerouting of failed signal units.
Ideally a restoration algorithm should restore a network failure quickly (within two seconds), require little administration overhead, handle numerous failure scenarios (not just single span cuts), be highly reliable, easily accommodate network growth, adapt itself to any network topology, and require a minimum amount of spare capacity. Of all restoration architectures, mesh restorable networks employing distributed dynamic path restoration have the greatest potential to satisfy these goals (as discussed in Fujii, H., Yoshikai, N., xe2x80x9cRestoration message transfer mechanism and restoration characteristics of double-search self-healing ATM networkxe2x80x9d, IEEE J-SAC Special Issue: Integrity of Public Telecommunication Networks, vol. 12, no. 1, Jan. ""94, pp. 149-158).
To date several centralized and distributed dynamic span restoration algorithms have been reported: Barezzani, M., Pedrinelli, E., Gerla, M., xe2x80x9cProtection planning in transmission networksxe2x80x9d, Proc. IEEE ICC""92, 1992, pp. 316.4.1-316.4.5. Chao, C. W., Fuoco, G., Kropfl, D., xe2x80x9cFASTAR platform gives the network a competitive edgexe2x80x9d, AT and T Technical Journal, July/August 1994, pp. 69-81. Chng, R. S. K., Botham, C. P., Johnson, D., Brown, G. N., Sinclair, M. C., O""Mahony, M. J. Hawker, I., xe2x80x9cA multi-layer restoration strategy for reconfigurable networksxe2x80x9d, Proc. IEEE Globecom ""94, December 1994, pp. 1872-1878. Chujo, T., Komine, H., Miyazaki, K., Ogura, T., Soejima, T., xe2x80x9cDistributed self-healing network and its optimum spare capacity assignment algorithmxe2x80x9d, Electronics and Communications in Japan, part 1, vol. 74, no. 7, 1991, pp. 1-8. Coan, B. A., Vecchi, M. P., Wu, L. T., xe2x80x9cA distributed protocol to improve the survivability of trunk networksxe2x80x9d, Proceedings of the 13th International Switching Symposium, May 1990, pp. 173-179. Coan, B. A., et al., xe2x80x9cUsing distributed topology updates and preplanned configurations to achieve trunk network survivabilityxe2x80x9d, IEEE Transaction on Reliability, vol. 40, no. 4, 1991, pp. 404-416. Of these Chng et al and Chujo et al claim the ability to perform path restoration. In general, any span restoration algorithm can be turned into a rudimentary path restoration scheme by iteratively applying the span restoration algorithm to all affected sourcexe2x80x94destination demand pairs. Using a span restoration algorithm to perform path restoration in this way was previously called Capacity Scavenging [Grover, W. D., Selfhealing Networksxe2x80x94A Distributed Algorithm for k-shortest link-disjoint paths in a multi-graph with applications in realtime network restoration, Ph.D. Dissertation, University of Alberta, Fall, 1989, referred to herein as the Grover Thesis]. While Capacity Scavenging can be used in path (and hence node) restoration, the recovery patterns obtained from uncoordinated concurrent (or arbitrary sequential) execution of a span restoration algorithm for every demand pair affected by a node or span failure may not yield an even allocation of recovery levels amongst affected demand pairs, or synthesize the maximum number of restoration paths topologically feasible.
While a few distributed dynamic path restoration algorithms have been reported [Chow, C. E., Bicknell, J. D., Mccaughey, S., xe2x80x9cPerformance analysis of fast distributed link restoration algorithmsxe2x80x9d, International Journal of Communication Systems, vol. 8, 1995, pp. 325-345, Doverspike, R. D., Morgan, J. A., Leland, W., xe2x80x9cNetwork design sensitivity studies for use of digital cross-connect systems in survivable network architecturesxe2x80x9d, IEEE J-SAC Special Issue: Integrity of Public Telecommunication Networks, vol. 12, no. 1, January ""94, pp. 69-78], none attempt to find a pathset which restores the maximum amount of lost demand topologically feasible. Distributed dynamic path restoration algorithms developed to date have focused on achieving restoration within the two second call-dropping threshold, and have given capacity efficiency secondary consideration.
The research presented here is unique in that it is the first distributed dynamic path restoration algorithm which attempts to configure the surviving spare links of a path restorable network to restore failed working paths in a capacity efficient manner, and do so within the two second call-dropping threshold, while achieving the other goals for path restoration of a mesh restorable network.
There is therefore provided a method and apparatus for establishing a communications path in a telecommunications network, in which the network is formed by plural nodes interconnected by plural spans, each span containing working and spare links, each node having a cross-connect switch for connecting links in spans terminating at the node and a controller for controlling propagation and content of statelets arriving at or transmitted from the node. In a first aspect of the invention, the method comprising the steps of:
propagating statelets through the network, in which each statelet comprises fields designating a source node for the statelet, a statelet index, and a measure of the spare capacity of spans traversed by the statelet;
updating each statelet transmitted from a node on a span, except at a destination node for that statelet, to alter the measure of spare capacity according to the spare capacity of the span on which the statelet is to be transmitted; and
creating a communications path through the nodes traversed by a statelet upon arrival of a statelet at the destination node of the statelet.
In a further aspect of the invention, the statelet comprises a field identifying the destination node of the statelet.
In a further aspect of the invention, the measure of spare capacity takes into account how many statelets are competing to be broadcast along the span and how many spare links in the span are available for broadcasting statelets.
In a further aspect of the invention, the measure of spare capacity is the difference between how many spare links in the span are available for broadcasting statelets and how many statelets are competing to be broadcast along the span.
In a further aspect of the invention, propagation of statelets is initiated upon receipt by a node in the network of a signal indicating that a working path in the network has failed.
In a further aspect of the invention, there is included the step of favouring use of spare links terminating at an end node of a failed working path by any statelet for which the destination node of the statelet is an end node of the failed working path.
In a further aspect of the invention, favouring use of spare links comprises:
defining a local protection area comprising nodes adjacent to an end node of a failed working path; and
updating a field in statelets traversing the local protection area in a manner that decreases the likelihood that the statelets will be broadcast from subsequent nodes if the destination node of the statelets is not the end node of the failed working path.
In a further aspect of the invention, favouring use of spare links comprises:
broadcasting statelets from first and second end nodes of a failed working path along respective paths until a statelet initiated by the first end node meets, at a tandem node, a statelet initiated by the second end node; and
propagating the statelet initiated by the first end node along the path followed by the statelet initiated by the second end node until the statelet reaches the second end node.
In a further aspect of the invention, there is provided the step of confirming the existence of a connected path between the first and second end nodes.
In a further aspect of the invention, each source node attempts to broadcast as many statelets, each corresponding to a different index family, as there are lost working paths.
In a further aspect of the invention, each statelet broadcast by a source node has an index field whose value is uniquely associated with the source and destination node of the statelet and the span on which the statelet is transmitted from the source node.
In a further aspect of the invention, each tandem node transmits on each span only one statelet having a specific combination of index field, source node and destination node.
In a further aspect of the invention, each tandem node attempts to broadcast each statelet arriving at the tandem node on as many spans as possible.
In a further aspect of the invention, each statelet contains a route field and the method further comprises the steps of:
each tandem node updating the route field of a statelet upon arrival of the statelet at the tandem node to include the identification of the tandem node, whereby the statelet contains a record of the nodes traversed by the statelet; and
preventing broadcast of each statelet to any tandem node previously traversed by the respective statelet.
In a further aspect of the invention, there is included the steps of:
identifying any communications paths having a length of one span; and
preventing any statelet from being broadcast along a communications path having a length of one span.
In a further aspect of the invention, creating a communications path comprises:
upon receipt of a statelet at a destination node, transmitting a reverse linking statelet from the destination node along the nodes traversed by the statelet.
In a further aspect of the invention, there is provided the step of cancelling transmission of a reverse linking statelet from a destination node if a reverse linking statelet having a given index field value arriving at a tandem node has traversed spans with lower spare capacity than another statelet with the given index field value competing to be broadcast from the tandem node.
In a further aspect of the invention, each statelet contains a repeat field and the method further comprises the steps of:
each tandem node incrementing the value of the repeat field of a statelet upon arrival of the statelet at the tandem node; and
preventing broadcast of statelets having a repeat field value greater than a pre-determined value.
There is also provided apparatus for carrying out the various aspects of the method of the invention.
These and other aspects of the invention are described in the detailed description of the invention and claimed in the claims that follow.